The present invention relates to methods and apparatus for managing the use of a finite number of resources among a plurality of requesters, such as the processors in a multi-processor system. By way of example, the present invention has applicability in a multiprocessor system in which tokens are used to allocate resources among a plurality of requesters.
There is an apparent insatiable desire for faster computer processing data throughputs, for example, because cutting-edge computer applications involve real-time, multimedia functionality. Graphics applications are among those that place the highest demands on a processing system because they require such vast numbers of data accesses, data computations, and data manipulations in relatively short periods of time to achieve desirable visual results. These applications require extremely fast processing speeds, such as many thousands of megabits of data per second. While some processing systems employ a single processor to achieve fast processing speeds, others are implemented utilizing multi-processor architectures. In multi-processor systems, a plurality of sub-processors can operate in parallel (or at least in concert) to achieve desired processing results.
In some existing multi-processor systems, a plurality of parallel processors may compete for a finite number of resources, such as one or more shared memories, I/O interfaces, etc. Resource management techniques are employed to allocate the resources among the processors for finite periods of time in order to ensure that each processor may use the resources. The conventional approach to managing the allocation of the resources may involve an arbiter of requests for the resources.
The requesters may be the respective processors in a multi-processor and the resources may be memory banks, I/O interfaces, etc. Tokens are mechanisms used to allocate blocks of time during which the requesters may use the resources. Thus, a given resource must obtain a token before it may issue a command (load, store, move, etc.) to a bus over which the resources may be accessed. Upon initialization of the system, the requesters may be assigned to groups (Group 0, Group 1, Group 2, etc.) by way of operating system software (or related software). A Token Manager (TM) receives tokens from the resources (specific sets of which are designated for respective ones of the requester groups), and grants tokens to the requesters on a round robin priority basis. The requesters may request a token on a high/low priority basis; thus, the TM grants the tokens to the requesters on a round robin basis as to high priority token requests and on a round robin basis as to low priority token requests.
Some of the requester groups may have a relatively low number of requesters assigned thereto, and in some cases one or more requester groups may be empty. Nevertheless, in accordance with existing systems, the TM still receives tokens designated for all of the requester groups. Thus, some of the requester groups (particularly the empty ones) may have an excess of tokens. Existing solutions to this inefficient distribution of tokens calls for establishing priorities for the requester groups that dictate the order in which excess tokens are re-distributed to the requester groups. A problem with this approach of token management is that the algorithm for establishing the priorities may be static or extremely slow, thereby resulting in an uneven and inefficient distribution and grant of tokens to the requesters. Indeed, some requester groups may deplete their tokens while others may have an excess of tokens despite having a redistribution algorithm in place. Thus, certain requesters may have to wait for a resource. This is wasteful if another group has one or more available tokens to the resource that are unused.